

In [ ]:

    
%%HTML
<style>
.container { width:100% }
</style>

Tic-Tac-Toe

This notebook defines the game tic-tac-toe. It is played on a $3 \times 3$ board. There are two players, which are called Xand O. Player X starts. Player X always puts an "X" into an empty field on the board, while player O always puts an "O" in an empty field of the board. The goal of the game for player X is to get three Xs into a row, column, or diagonal line, while player O needs to get three Os into a row, column, or diagonal line.



In [ ]:

    
Players = [ "X", "O" ]

States are represented as tuples of tuples. The game starts with an empty board. An empty field on the board is represented as the string " ".



In [ ]:

    
Start = tuple( tuple(" " for col in range(3)) for row in range(3))
Start

The function to_list transforms a tuple of tuples into a list of lists.



In [ ]:

    
to_list = lambda State: [list(row) for row in State]

The function to_tuple transforms a list of lists into a tuple of tuples.



In [ ]:

    
to_tuple = lambda State: tuple(tuple(row) for row in State)

Given a state S the function empty(S) returns the list of pairs (row, col) such that S[row][col] == ' ' holds. These pairs are the coordinates of the fields on the board S that are not yet occupied by either an "X" or an "O".



In [ ]:

    
def empty(S):
    return [ (row, col) for row in range(3)
                        for col in range(3)
                        if  S[row][col] == ' ' 
           ]

Given a State and the player who has the next move, the function next_states(State, player) computes the set of states that can be reached from State.



In [ ]:

    
def next_states(State, player):
    Empty  = empty(State)
    Result = []
    for row, col in Empty:
        NextState           = to_list(State)
        NextState[row][col] = player
        Result.append( to_tuple(NextState) )
    return Result

The variable All_Lines is a collects the coordinates of all the fields of the three rows, the three columns, and the two diagonals. This variable is needed to check whether any player has won the game.



In [ ]:

    
All_Lines = [ [ (row, col) for col in range(3) ] for row in range(3) ] \
          + [ [ (row, col) for row in range(3) ] for col in range(3) ] \
          + [ [ (idx,   idx) for idx in range(3) ] ]                   \
          + [ [ (idx, 2-idx) for idx in range(3) ] ]
All_Lines

The function utility takes two arguments:

State is a tuple of tuple representing the board.
player is a player.

The function returns 1 if player has won the game, -1 if the game is lost for player, 0 if its a draw, and None if the game has not yet been decided.



In [ ]:

    
def utility(State, player):
    for Pairs in All_Lines:
        Marks = { State[row][col] for row, col in Pairs }
        if len(Marks) == 1 and  Marks != { ' ' }: 
            if Marks == { player }:
                return  1
            else:
                return -1
    for row in range(3):
        for col in range(3):
            if State[row][col] == ' ':
                return None   
    # the board has to be filled now, but there is no winner
    return 0

The function heuristic tries to guess the value of a state. As it is never called in terminal states, it assumes that the game will be drawn.



In [ ]:

    
def heuristic(State, player):
    return 0

finished(State) is True if the game is over.



In [ ]:

    
finished = lambda State: utility(State, "X") != None

The function get_move asks the user to input a move in the format r,c where r is the row and the c is the column where the next symbol is to be placed.



In [ ]:

    
def get_move(State):
    State = to_list(State)
    while True:
        row, col = input("Enter move here: ").split(",")
        row, col = int(row), int(col)
        if State[row][col] == ' ':
            State[row][col] = 'O'
            return to_tuple(State)
        else:
            print("Don't cheat.  Please try again.")

This function informs the user about the result of the game once the game is finished.



In [ ]:

    
def final_msg(State):
    if finished(State):
        if utility(State, "O") == 1:
            print("You have won!")
        elif utility(State, "O") == -1:
            print("You have lost!")
        else:
            print("It's a draw.");
        return True
    return False

Drawing the Board



In [ ]:

    
import ipycanvas as cnv



In [ ]:

    
size = 150

This function creates the canvas for the start state. It draws an empty board which is later used for the game.



In [ ]:

    
def create_canvas(Start):
    n = len(Start)
    canvas = cnv.Canvas(size=(size * n, size * n + 50))
    display(canvas)
    return canvas

This function takes three arguments:

State is the current state of the game.
canvas is a canvas used to draw the state.
value is the value of the game for player X.

The function draws the given State onto canvas. Below that, the value is printed.



In [ ]:

    
def draw(State, canvas, value):
    canvas.clear()
    n = len(State)
    canvas.font = '90px sans-serif'
    canvas.text_align    = 'center'
    canvas.text_baseline = 'middle'
    for row in range(n):
        for col in range(n):
            x = col * size
            y = row * size
            canvas.line_width = 3.0
            canvas.stroke_rect(x, y, size, size)
            symbol = State[row][col]
            if symbol != ' ':
                x += size // 2
                y += size // 2
                if symbol == 'X':
                    canvas.fill_style ='red'
                else:
                    canvas.fill_style ='blue'
                canvas.fill_text(symbol, x, y)
    canvas.font = '20px sans-serif'
    canvas.fill_style = 'black'
    x = 1.5 * size
    y = 3.2 * size
    canvas.fill_text(str(value), x, y)



In [ ]: